Given a directed graph G and two vertices $s$ and $t$, use a max-flow solver to compute the maximum number of edge-disjoint $s-t$ paths. Can you extend your approach to compute the maximum number of vertex-disjoint $s-t$ paths? \\

\textbf{Edge-disjoint paths}\\

In order to calculate the maximum number of edge-disjoint paths we have to assign to all edges the capacity of one. By doing this we assure that the number of augmenting paths across any edge is at most one. This is true because only one augmenting path from $s$ to $t$ can traverse the same edge. After running the maxflow algorithm, the number of edge-disjoint paths will be equal to the maxflow, because each augmenting path will propagate a flow of value one. So the number of edge-disjoint paths will be equal to the number of augmenting paths (which are edge-disjoint since the edges have capacity one).\\

\textbf{Vertex-disjoint paths}\\

One easy solution is to transform every vertex into two vertices in order to define a directed edge. Let's say that we have some edges pointing to a vertex and others coming out. We'll convert the single vertex into a two vertices in a way presented in the following picture:

\begin{center}
\includegraphics[scale=0.5]{get-cut-2.png}  
\end{center}

This will allow us to apply the same idea as in the first solution. It should also be noticed that suggested changing of the graph doesn't create new augmenting paths from $s$ to $t$, but only constrains their amount. Since all the capacities will be one, the number of edge-disjoint paths will be equal to the maximum flow. But in our case, since we have transformed each vertex into an edge, we assure that the number of vertex-disjoint paths is defined by the number of edge-disjoint paths. This is true because no two augmenting paths will traverse the same vertex. \\

